// https://leetcode.cn/problems/contains-duplicate-ii/description/

// 算法思路总结：
// 1. 使用哈希表记录数字和最近出现索引
// 2. 遍历数组，检查当前数字是否出现过
// 3. 如果出现过且索引差≤k，返回true
// 4. 否则更新该数字的最近出现索引
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <unordered_map>
#include <cstdlib>

class Solution 
{
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) 
    {
        int n = nums.size();
        unordered_map<int, int> up;

        for (int i = 0 ; i < n ; i++)
        {
            if (up.count(nums[i]) > 0 && abs(up[nums[i]] -  i) <= k)
                return true;
            
            up[nums[i]] = i;
        }

        return false;
    }
};

int main()
{
    vector<int> v1 = {1,2,3,1}, v2 = {1,2,3,1,2,3};
    int n1 = 3, n2 = 2;
    
    Solution sol;
    cout << sol.containsNearbyDuplicate(v1, n1) << endl;
    cout << sol.containsNearbyDuplicate(v2, n2) << endl;

    return 0;
}